package com.wlc.collection;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 王立朝 wanglichao@champion-credit.com
 * @description 二叉树
 * @date 2021-07-12 08:04
 */
public class BinaryTree {
    // 左子节点
    public BinaryTree leftNode;
    // 右子节点
    public BinaryTree rightNode;
    // 值
    public Object value;

    /**
     * 生成40000个随机数
     * @return
     */
    public int[] getNumbers() {
        //初始化随机数
        int total = 10;
        System.out.println("初始化一个长度是" + total + "的随机数字的数组");
        int[] originalNumbers = new int[total];
        for (int i = 0; i < originalNumbers.length; i++) {
            originalNumbers[i] = (int) (Math.random() * total);
        }
        return originalNumbers;
    }

    public void sortTime(){
        int[] numbers = getNumbers();
        for (int i = 0; i < numbers.length; i++) {
            System.out.print("" + numbers[i]+ " ");
        }
        System.out.println("  ");
        BinaryTree binaryTree = new BinaryTree();
        long start = System.currentTimeMillis();
        for (int i = 0; i < numbers.length; i++) {

            binaryTree.addBinaryTree(numbers[i]);
        }
        List<Object> sort = binaryTree.sort();
        System.out.println("sort.size() = " + sort.size()+" 排序后的结果为："+sort.toString());


        long end = System.currentTimeMillis();
        long time = end - start;
        System.out.println("排序时间为： " + time);
    }

    /**
     * 二叉树
     * 比当前数小或者等于当前数，放在左节点；
     * 比当前数大，放在右节点；
     * 如果左节点没有值，就放在左节点；如果右节点没有值，就放在右节点
     */
    public void method01() {
        int[] numbers = new int[]{23, 15, 34, 100, 45, 24, 26, 2, 5};
        BinaryTree binaryTree = new BinaryTree();
        for (int i = 0; i < numbers.length; i++) {
            binaryTree.addBinaryTree(numbers[i]);
        }
        System.out.println("binaryTree.sort() = " + binaryTree.sort());

    }

    /**
     * 把数据放入二叉树节点
     * 逻辑：
     *    当前节点是否为空，如果为空，则把当前节点的数据赋值给传入的数据；
     *   如果当前节点不为空，
     *      判断 当前节点 和 比较的数的大小，  如果  当前节点 <= 比较的数，   放入右节点；
     *                                     如果  当前节点 > 比较的数   放入左节点
     * @param number
     */
    public void addBinaryTree(Object number) {
        // 如果当亲啊节点没有值，就把number 当前值放在节点上面
        if (null == value) {
            value = number;
        } else {
            // 当前节点有值
            // 判断新增的数和当前节点的关系；小于或者等于放在左节点
            if (((Integer) number) - (Integer) value <= 0) {
                if (null == leftNode) {
                    leftNode = new BinaryTree();
                }
                leftNode.addBinaryTree(number);
            } else {
                // 新增的数比当前节点大，放在右节点上面
                if (null == rightNode) {
                    rightNode = new BinaryTree();
                }
                rightNode.addBinaryTree(number);
            }
        }


    }

    /**
     * 二叉树排序
     * @return
     */
    private List<Object> sort() {
        List<Object> objects = new ArrayList<>();
        if (null != leftNode) {
            objects.addAll(leftNode.sort());
        }
        objects.add(value);
        if (null != rightNode) {
            objects.addAll(rightNode.sort());
        }
        return objects;
    }

    public static void main(String[] args) {
        new BinaryTree().sortTime();
    }


}
